"""
Game
Copyright (C) 2007 Andrew Briscoe

A module used to describe a board game.
"""

__license__ = 'GPL http://www.gnu.org/licenses/gpl.txt'
__author__ = 'Andrew Briscoe <everynothing@gmail.com>'
__version__ = '0.0.1'
__program__ = 'PIGS'

import copy

class Coord(object):
    'Board coordinate'

    def __init__(self, row=None, col=None):

        self.row, self.col = row, col
    
    def direction(self, pos2):
        'Returns a coordinate that is the direction form pos1 to pos2'

        return Coord(cmp(pos2.row, self.row), cmp(pos2.col, self.col))
    
    def distance(self, pos2):
        'Returns a coordinate that is the direction form pos1 to pos2'
        
        dists = [abs(a) for a in [self.row - pos2.row, self.col - pos2.col]]
        return dists[0] if dists[0] >= dists[1] else dists[1]
    
    def multiply(self, times):
        'A coordinate thats values are selfs multiplied by times.'
        
        return Coord(self.row * times, self.col * times)

    def on_board(self, board):
        'Returns True if the coordinate is in the given board.'

        return (0 <= self.col < board.cols) and (0 <= self.row < board.rows)
        
    def in_range(self, rhs, disntance):
        'Is the distance from self to rhs less than distance?'
        
        return abs(self.row-rhs.row) <= disntance and \
            abs(self.col-rhs.col) <= disntance
            
    def mirror(self):
        'Returns a corrd with rows and cols switched.'
        
        return Coord(self.col, self.row)

    def __eq__(self, rhs):
        return rhs and self.col == rhs.col and self.row == rhs.row

    def __add__(self, rhs):
        return Coord(self.row + rhs.row, self.col + rhs.col)

    def __sub__(self, rhs):
        return Coord(self.row - rhs.row, self.col - rhs.col)
    
    def __str__(self):
        return str(self.row) + ' ' + str(self.col)

#Magic numbers
KO,  THREE_TIMES, INFINITE, DEFAULT, DRAW = \
352, 324,         9999,     941,     525
#Base Directions
UP,           DOWN,        LEFT,         RIGHT = \
Coord(-1, 0), Coord(1, 0), Coord(0, -1), Coord(0, 1)
#Secondary Directions
UP_LEFT, UP_RIGHT, DOWN_LEFT, DOWN_RIGHT = \
UP + LEFT, UP + RIGHT, DOWN + LEFT, DOWN + RIGHT
#Territry Directions
STRAIT_DIRECTIONS,       DIAGONAL_DIRECTIONS = \
(UP, DOWN, LEFT, RIGHT), (UP_LEFT, UP_RIGHT, DOWN_LEFT, DOWN_RIGHT)
ALL_DIRECTIONS = (STRAIT_DIRECTIONS + DIAGONAL_DIRECTIONS)

class Piece(object):
    'Base class for a piece. If not subclassed its an empty square.'
    
    CAN_MAKE_CAPTURES     = False
    CAN_BE_CAPTURED       = True
    MOVEABLE_DIRECTIONS   = ()
    RANGE                 = 0
    BLANK                 = True
    TYPE                  = 'Empty'

    def __init__(self, color=None, position=None):
        self.color = color
        self.position = position
        
    def __eq__(self, other):
        'Returns True if all the attributes of other are the same as self'
        
        return self.TYPE == other.TYPE and self.color == other.color and \
            self.position == other.position

    def potential_moves(self, board):
        'An iterator over all moves this piece can do.'
        
        pass
        
    def can_capture(self, piece):
        'Can self capture piece?'
        
        return not self.color is piece.color and \
            piece.CAN_BE_CAPTURED and self.CAN_MAKE_CAPTURES
    
    def enemey(self, piece):
        'Is piece selfs enemey?'
        
        return not piece.BLANK and not self.BLANK \
            and not self.color is piece.color
            
    def duplicate(self, piece):
        """Copies the attributes of another piece. 
        This is typically used when a pawn is promoted."""
        
        self.color, self.position = piece.color, piece.position
        return self
    
    def __str__(self):
        
        return str(self.TYPE) + ' ' + str(self.color)

class FilledPiece(Piece):
    'Base class for any piece other than an empty sqaure.'
    
    BLANK = False

class MovingPiece(FilledPiece):
    'A piece that can move.'

    CAN_MAKE_CAPTURES = True
    RANGE             = INFINITE
    
    def __init__(self, color, position = None):
        
        FilledPiece.__init__(self, color, position)
        self.has_moved = False
        
    def do_move(self, board, move):
        """Same as a regular pieces move, but sets has moved 
        and blows up if the capture was a grenade"""
        
        if move.capture:
            board.capture(move.destination)
        board.just_move(self.position, move.destination)
        self.has_moved = True

    def potential_moves(self, board, directions=DEFAULT, distance=DEFAULT):
        'Return an iterable of all potential moves this piece has.'
        
        if directions is DEFAULT:
            directions = self.MOVEABLE_DIRECTIONS
        if distance is DEFAULT:
            distance = self.RANGE
        for piece in board.walk_in_directions( \
           self.position, directions, distance, True):
            cap = None if piece.BLANK else piece
            if piece.BLANK or self.can_capture(piece):
                yield board.gen_move(self.position, piece.position, cap, False)
        
    def player_can_move(self, board, player):
        'Can player move self?'
        
        return self.color == player
    
class PieceList(object):
    'A list of pieces with a name and an ammount.'
    
    def __init__(self, color):
        
        self.captures, self.color = [], color
        
    def __eq__(self, other):
        'Is this capture list the same as other?'
        
        return self.captures == other.captures
        
    def add_capture(self, name):
        'Adds a capture to this piece list'
        
        cap = self.get(name)
        if cap is not None:
            cap[1] += 1
        else: self.captures += [[name, 1]]

    def remove_capture(self, name):
        'Removes a capture of name from this hand and returns it.'
        
        return self.get(name, True)
        
    def get(self, name, pop = False):
        """Returns the captured piece objeect of name in 
        this piece list. If pop it removes it."""
        
        for cap in self.captures:
            if cap[0] == name:
                if pop:
                    if cap[1] > 1:
                        cap[1] -= 1
                    else: self.captures.pop(cap)
                return cap
        return None


class Board(object):
    'A State of a board game.'
    
    #The game type, changes in all subclasses.
    GAME_TYPE             = 'None'
    #The game variant, regular if not a variant.
    VARIANT_TYPE          = 'Regular'
    #What happens when a player tries to repeat a position?
    REPITITION_RULE       = KO
    #The pieces that can be on this board.
    POSSIBLE_PIECES       = []
    #How player numbers translate to strings.
    COLORS                = ['White', 'Black', 'Blue', 'Green', 'Neutral']
    #What boards can this game be played on?
    POSSIBLE_BOARDS       = []
    #What variations of this game are there?
    POSSIBLE_VARIANTS     = ["Regular"]

    def __init__(self, rows, cols, players, board_name):
        
        self.rows         = rows
        self.cols         = cols
        self.turn         = 0
        self.players      = players
        self.board_name   = board_name
        self.force_win    = None
        self.last_action  = None
        self.captures     = [PieceList(p) for p in xrange(players)]
        self.squares      = tuple([Piece(None, Coord(b, a)) \
           for a in xrange(cols)] for b in xrange(rows))
    
    def __eq__(self, other):
        'Returns True if all the attributes of self are the same as other'
        
        return self._same_size(other) and self._same_pieces(other)
    
    def _same_position(self, other):
        'Are the pieces on the board the same as on other?'
        
        return self._same_size(other) and self._same_pieces(other)
            
    def _same_size(self, other):
        'Is self the same size as other?'
        
        return self.rows == other.rows and self.cols == other.cols
    
    def _same_pieces(self, other):
        'Are the pieces and self and other the same?'
        
        return not [1 for piece in self if \
                    (not piece == other[piece.position])]

    def __getitem__(self, place):
        'Returns the square on the given coordinate.'

        return None if not place.on_board(self) \
            else self.squares[place.row][place.col]

    def __contains__(self, coord):
        'Returns True if the coordinate is in the board.'

        return coord.on_board(self)

    def __iter__(self):
        'Returns an iterator over all the squares in self'
        
        for row in xrange(self.rows):
            for col in xrange(self.cols):
                yield self.squares[row][col]
            
    def capture(self, coord):
        'Adds coord to captures if its not empty, and then kills it'
        
        piece = self._remove_piece(coord)
        if not piece.BLANK:
            self.captures[self._next_player(piece.color)].add_capture(piece.TYPE)

    def _col(self, col):
        'Returns an iterator of all the pieces in a given column.'

        for row in range(0, self.rows):
            yield self[Coord(row, col)]
        
    def clone(self):
        'Returns an identical copy to self.  maybe change later'
        return copy.deepcopy(self)

    def _edges(self):
        'Returns an iterator of all the edges of the board'
        
        for edge in [self._row(0), self._col(0), \
             self._row(self.rows - 1), self._col(self.cols - 1)]:
            for square in edge:
                yield square

    def _end_turn(self):
        'Ends the current turn'
        
        self.turn = self._next_player(self.turn)

    def just_move(self, pos1, pos2):
        'Just shifts the piece from pos1 to pos, and returns self'
        
        self.place_piece(pos2, self._remove_piece(pos1))

    def _kill(self, coord):
        'Clears square coord'
        
        self.place_piece(coord, Piece())

    def _manufacture_piece(self, piece_name, color):
        'Manufactures a piece from a string in this boards POSSIBLE PIECES'
        
        return self.POSSIBLE_PIECES[piece_name](color) \
            if piece_name in self.POSSIBLE_PIECES else None
            
    def _manufacture_pieces(self, piece_list, color):
        'Manufactures a list of pieces from strings of a certain color.'
    
        return [self._manufacture_piece(piece, color) for piece in piece_list]

    def message(self):
        'Returns a status message for this Board'
        
        def ongoing_message():
            'The message if the game is still happening.'
            
            return "Playing %s %s on a %s board."% \
                (self.VARIANT_TYPE, self.GAME_TYPE, self.board_name)
                
        def over_message():
            'The message if the game is over'
            
            winner = self.who_won()
            return 'Game drawn.' if winner is DRAW \
                else self.COLORS[winner] + ' has won the game!'
        
        return ongoing_message() if not self.game_over() else over_message()
    
    def locate_piece(self, coord, distance=1, typ=DEFAULT, col=DEFAULT):
        """If a piece of type and color is in range, 
        return true.  False otherwise."""
        
        return self.find_piece(typ, col, 
           self.squares_in_range(coord, distance))
    
    def find_piece(self, typ=DEFAULT, col=DEFAULT, itr=DEFAULT):
        """If a piece of type and color is in range, 
        return true.  False otherwise."""
        
        if itr is DEFAULT:
            itr = self
        for piece in itr:
            if (piece.TYPE is typ or typ is DEFAULT) and \
                (piece.color is col or col is DEFAULT):
                return piece
        return None

    def neighbors(self, coord, directions=ALL_DIRECTIONS):
        'Returns an iterator over all the squares next to this one (Strait)'
        
        for direction in directions:
            square = self[direction + coord]
            if square:
                yield square

    def _next_player(self, player=DEFAULT):
        'Returns the player that moves after player'
        
        if player is DEFAULT:
            player = self.turn
        return 0 if player is self.players - 1 else player + 1

    def place_piece(self, coord, piece):
        'Places a piece on the given coordinate and then returns it.'
        
        if coord.on_board(self):
            self.squares[coord.row][coord.col] = piece
        piece.position = coord
        return piece

    def place_pieces_on_board(self, pieces, coord, direction):
        """Places a list of pieces onto this board, starting at coord 
        and going in dirsction"""
    
        for piece in self.walk_in_direction(coord-direction, direction):
            if not not pieces:
                self.place_piece(piece.position, pieces.pop(0))
    
    def _remove_piece(self, coord):
        'Removes the piece from a coordinate, and returns it.'

        piece = self[coord]
        self._kill(coord)
        return piece

    def _remove_player(self, col):
        'Clears the board of all pieces of color col'
        
        for piece in self:
            if piece.color == col:
                self._kill(piece.position)
    
    def gen_move(self, start, finish, capture=None, real=False):
        'Generates the move from pos to destination.'
        
        return []
    
    def legal_moves(self, piece = None, color = DEFAULT):
        'All moves that are legal.'
        
        return []
    
    def last_action_loc(self):
        'Where was the finishing square of the last move or drop?'
        
        act = self.last_action
        return [getattr(act, a) for a in ['position', 'destination'] \
            if hasattr(act, a)]
    
    def _row(self, row):
        'Returns an iterator of all the pieces in a given row.'

        for col in range(0, self.cols):
            yield self[Coord(row, col)]
    
    def set_blank(self):
        'Sets squares to be a list of None, rowsXcolums'

        for square in self:
            self.place_piece(square.position, Piece())
            
    def squares_in_range(self, coord, distance):
        """Returns an iterator over the pieces next to
        coord in this boards squares"""
        
        def one_offset(i):
            'Returns a range of the squares next to i, +1 because inclusive.'
            
            return xrange(i - distance, i + distance + 1)
        
        for row in one_offset(coord.row):
            for col in one_offset(coord.col):
                piece = self[Coord(row, col)]
                if piece and not piece.position == coord:
                    yield piece
    
    def walk_in_direction(self, coord, direction, distance=INFINITE, 
                          stop_hit=False):
        """Returns an iterator over all the pieces in the given direction
        from an initial position with a max ammount of distance.
        If stop hit, when it hits something it stops."""
        
        for counter in xrange(1, INFINITE):
            coord += direction
            if counter > distance or not coord in self:
                break
            yield self[coord]
            if stop_hit and not self[coord].BLANK:
                break
            
    def walk_in_directions(self, coord, dirs, dist=INFINITE, stop=False):
        'Same as walk in direction, but for many directions.'
        
        if dirs:
            for direc in dirs:
                for piece in self.walk_in_direction(coord, direc, dist, stop):
                    yield piece
        
    def walk_til_hit(self, coord, direction, distance=INFINITE):
        'Returns the first thing walk in direction hits, None otherwise.'
        
        walk = list(self.walk_in_direction(coord, direction, distance, True))
        return walk[-1] if walk and not walk[-1].BLANK else None

    def who_won(self):
        'Who won the game?'
        
        return self.players
            
    def _alter_piece_class(self, piece, new_type, color = DEFAULT):
        'Turns a piece into a new piece with the same attributes.'
        
        if color == DEFAULT:
            color = piece.color
        self.place_piece(piece.position, \
            self._manufacture_piece(new_type, color).duplicate(piece))
            
    def game_over(self):
        'Is the game finished based on the board state? Changes in subclasses.'
        
        return True
    
    def do_move(self, move):
        'Move a piece from coord1 to coord2 and ends the turn.'
            
        self[move.position].do_move(self, move)
        self._end_turn()
    
    def do_drop(self, drop):
        'Drops a piece on a square and ends the turn.'
        
        self.place_piece(drop.position, drop.piece)
        self._end_turn()
    
    def do_resign(self, res):
        'What happens when someone resigns.'
        
        if not self.players > 2:
            self.force_win = self._next_player(res.player)
        else:
            self._remove_player(res.player)
    
    def do_pass(self):
        'A player chooses not to move.'
        
        self._end_turn()
    
    def do_draw(self):
        'The game is now a draw'
        
        self.force_win = DRAW
        
    def is_move_legal(self, move):
        'By default moves are illegal.'
        
        return False
    
    def is_drop_legal(self, drop):
        'By default drops are illegal.'
        
        return False
    
    def is_resign_legal(self):
        'By default resignation is legal.'
        
        return True
    
    def is_draw_legal(self):
        'By default drawing is legal.'
        
        return True
    
    def is_pass_legal(self):
        'By default passing is illegal.'
        
        return False
    
def action_from_string(act_str, board):
    "Take some strings and return an action."
    
    def crd(str1, str2):
        "Make a coord from strings."
        
        return Coord(int(str1), int(str2))
    
    tok = act_str.split(' ')
    typ = tok[0]
    if typ == 'Move':
        return board.gen_move(crd(tok[1], tok[2]), crd(tok[3], tok[4]))
    elif typ == 'Drop':
        return Drop(crd(tok[1], tok[2]), 
                    board._manufacture_piece(tok[3], int(tok[4])))
    elif typ == 'Resign':
        return Resign(int(tok[1]))
    elif typ == 'Pass':
        return Pass()
    elif typ == 'Draw':
        return Draw()
    elif typ == "Take":
        return TakeBack()
    
class Action(object):
    'Any action that can be taken on a board.'
    
    #Can players whose turn it is do this action?
    ONLY_CURRENT = True
    
    def __init__(self):
        'Add stuff such as time this action was performed later'
        
        pass
    
    def do_action(self, board):
        """Clones a board, makes its last action self, 
        and makes board execute self."""
        
        clone = board.clone()
        clone.last_action = self
        self.execute(clone)
        return clone
    
    def execute(self, board):
        'What happens when this action executes.'
        
        pass
    
    def legal(self, board):
        'Is this action legal on board?'
        
        pass
    
    def __str__(self):
        
        return ""
        
class Move(Action):
    'Contains the information to describe a piece move.'

    PLAIN = 0
    
    def __init__(self, position, destination, capture=None, move_type=PLAIN):
        
        Action.__init__(self)
        self.position     = position
        self.destination  = destination
        self.capture      = capture
        self.type         = move_type
            
    def __eq__(self, other):
        'Is this move the same as other?'
        
        return self.position == other.position and \
            self.destination == other.destination and \
            self.capture == other.capture and self.type == other.type
        
    def direction(self):
        'The direction this move is in'
        
        return self.position.direction(self.destination)
    
    def execute(self, board):
        'What happens when this move is made.'
        
        board.do_move(self)
    
    def legal(self, board):
        'Is this move legal on board?'
        
        return board.is_move_legal(self)
    
    def __str__(self):
        
        return "Move " + str(self.position) + " " + str(self.destination)
        
class Drop(Action):
    'Contains the information to describe a piece drop.'
    
    def __init__(self, position=None, piece=None):
        
        Action.__init__(self)
        self.position = position
        self.piece = piece
        
    def execute(self, board):
        'What happens when a player makes this drop.'
        
        board.do_drop(self)
    
    def legal(self, board):
        'Can the current player make this drop?'
        
        return board.is_drop_legal(self)
    
    def __str__(self):
        
        return "Drop " + str(self.position) + " " + str(self.piece)
        
class Pass(Action):
    'A player chooses not to move.'
    
    def execute(self, board):
        'What happens when a player passes.'
        
        board.do_pass()
    
    def legal(self, board):
        'Can players pass?'
        
        return board.is_pass_legal()
    
    def __str__(self):
        
        return "Pass"
        
class Resign(Action):
    'A player resigns.'
    
    ONLY_CURRENT = False
    
    def __init__(self, player):

        Action.__init__(self)
        self.player = player
        
    def execute(self, board):
        'What happens when a player resigns.'
        
        board.do_resign(self)
    
    def legal(self, board=None):
        'A player can always resign.'
        
        return board.is_resign_legal()
    
    def __str__(self):
        
        return "Resign " + str(self.player)
        
class Draw(Action):
    'Players have agreed on a draw.'
    
    ONLY_CURRENT = False
    
    def execute(self, board):
        'Players have agreed on a draw.'
        
        board.do_draw()
    
    def legal(self, board):
        'Players can always agree to a draw.'
        
        return board.is_draw_legal()
    
    def __str__(self):
        
        return "Draw"
    
class TakeBack(Action):
    'A player resigns.'
    
    ONLY_CURRENT = False
    
    def legal(self, board=None):
        'A player can always resign.'
        
        return True
    
    def __str__(self):
        
        return "Take Back"

class Node(object):
    'A board and all the boards after it.'
    
    def __init__(self, parent, board):
        
        self.board = board
        self.branches = []
        self.parent = parent
        self.depth = parent.depth + 1 if parent else 1
        
    def add_branch(self, board):
        'Adds a new branch with board in it, if its not already there.'
        
        for branch in self.branches:
            if branch.board == board:
                self.branches.remove(branch)
        to_add = Node(self, board)
        self.branches.insert(0, to_add)
        return to_add
    
    def __str__(self):
        "Represent this node as a string."
        
        act = self.board.last_action
        ret = str(act) + ';' if act else ''
        if self.branches:
            for var in self.branches[1:]:
                ret += '(' + str(var) + ')'
            ret += str(self.branches[0])
        return ret

class Game(object):
    'The class that defines the entire game.'
    
    def __init__(self, board):
        
        self.starting_position = Node(None, board)
        self.go_to_starting_position()
        self.players = board.players
        self.COLORS = copy.deepcopy(board.COLORS)
        self.board_name = board.board_name
        self.rows = board.rows
        self.cols = board.cols
        self.game_type = board.GAME_TYPE
        self.variant_type = board.VARIANT_TYPE
        
    def set_current_node(self, node):
        'Set the current board position.'
        
        self.current_node = node
        self.board = node.board
        
    def execute_action(self, action):
        'Adds a new branch to current node with action executed.'
        
        if str(action) == "Take Back":
            self.take_back_move()
        else:
            node = self.current_node.add_branch(action.do_action(self.board))
            if self.threefold_repetition_detected(node.board):
                node.board.force_win = DRAW
            self.set_current_node(node)
            
    def action_legal(self, action):
        'Is action legal on the current board?'
        
        return action.legal(self.board) and not \
            self.board_illegal_by_ko(action.do_action(self.board))
                                                                         
    def go_to_starting_position(self):
        'Sets current node to starting position'
        
        self.set_current_node(self.starting_position)
        
    def go_to_end(self):
        'Goes to the end of the deepest variation from the current position.'
        
        while self.current_node.branches:
            self.set_current_node(self.current_node.branches[0])
        
    def take_back_move(self):
        'Takes back the current move but leaves the variation.'
        
        par = self.current_node.parent
        if par:
            self.set_current_node(par)
        
    def board_illegal_by_ko(self, board):
        'Is action legal on the current board?'
        
        return self.current_node.depth > 5 and board.REPITITION_RULE == KO and \
            self.position_same(board, self.current_node.parent)
            
    def threefold_repetition_detected(self, board):
        'Was the same position repeated three times?'
        
        par = self.current_node.parent
        return self.current_node.depth > 5 and \
            board.REPITITION_RULE == THREE_TIMES and \
            self.position_same(board, par) and \
            self.position_same(board, par.parent.parent)
            
    def position_same(self, board, previous_node):
        'Does the move make the same position?'
        
        return hasattr(board.last_action, 'position') and \
            board == previous_node.board
            
    def message(self):
        'Just aliases the current boards message for easy access.'
        
        return self.board.message()
    
    def game_over(self):
        'Just aliases the current boards game_over() for easy access.'
        
        return self.board.game_over()
    
    def turn(self):
        "Just aliases board.turn for easy access."
        
        return self.board.turn
    
    def __str__(self):
        "Store this game as a string."
        
        return ','.join([self.game_type, self.board_name, 
                         self.variant_type, str(self.starting_position)])